//
// Created by yunlang on 2021/12/8.
//
#include <iostream>
#include "PriorityQueue.h"
#include "TreeNode.h"
#include "limits.h"
using namespace std;
const unsigned int PriorityQueue::CAPACITY = 1000000;
PriorityQueue::PriorityQueue()
{
    data = (TreeNode**) malloc((CAPACITY + 1) * sizeof(TreeNode*));
    for(int i = 0; i < CAPACITY; i++)
    {
        data[i] = (TreeNode*)malloc(sizeof(TreeNode));
    }
    if(!data)
    {
        cout << "error" << endl;
    }
    size = 0;
    data[0]->weight = 0;
}

PriorityQueue::~PriorityQueue()
{
    while(getSize() > 0)
        pop();
}

//template<class T>
int PriorityQueue::getSize()
{
    return size;
}

//template<class T>
void PriorityQueue::push(TreeNode* key)
{
    if(getSize() == 0)
    {
        data[++size] = key;
        return;
    }
    if(getSize() == CAPACITY)
    {
        cout << "Full" << endl;
        return;
    }
    int i;
    for( i = ++size; data[i/2]->weight > key->weight; i/=2 )
    {
        data[i] = data[i/2];
    }
    data[i] = key;
}

//template<class T>
void PriorityQueue::pop()
{
    if(getSize() == 0)
    {
        cout << "error" << endl;
        return;
    }
    TreeNode* last = data[size--];
    TreeNode* min = data[1];
    unsigned int i;
    unsigned int child;
    for( i = 1; i * 2 <= size; i = child )
    {
        child = i * 2;
        if( child != size && data[child]->weight < data[child+1]->weight )
            child++;
        if( last->weight > data[child]->weight )
            data[i] = data[child];
        else
            break;
    }
    data[i] = last;
}

//template<class T>
TreeNode* PriorityQueue::top()
{
    if(getSize() == 0)
    {
        cout << "Empty" << endl;
        return data[0];
    }
    return data[1];
}